package com.lwt.codetop.dp;

//42. 接雨水

/**
 * 思路一：前后缀最值预处理（递推/dp）
 *
 * 思路二：单调栈（TODO）
 */
public class TrappingRainWater {
    public static void main(String[] args) {
        // 构建测试用例
        int[]  height = {0,1,0,2,1,0,1,3,2,1,2,1};
        int res = trap(height);
        System.out.println(res);
    }

    /**
     * 思路一：前后缀最值预处理求所接雨水的总量
     *      left[i]/right[i]：当前柱子左边/右边最高的柱子的高度为left[i]/right[i]
     *      当前位置可以接到的雨水 min(left[i], right[i]) - curH, 且curH低的情况下， 然后进行累加即可
     * @param height
     * @return
     */
    private static int trap(int[] height) {
        int n = height.length;
        int[] left = new int[n + 10];
        int[] right = new int[n + 10];
        int res = 0;
        // 预处理每根柱子左右两边最高的柱子高度
        for(int i = 1; i < n; i ++){
            left[i] = Math.max(left[i - 1], height[i - 1]);
        }
        for(int i = n - 2; i >= 0; i --){
            right[i] = Math.max(right[i + 1], height[i + 1]);
        }
        // 求雨水面积
        for(int i = 0; i < n; i ++){
            int minH = Math.min(left[i], right[i]);
            if(minH > height[i]) res += (minH - height[i]);
        }
        return res;
    }
}
